#include "ai.h"

/* Globals */
int rows;
int cols;
int last_move;
int total_time;
int player_1_time;
int last_move_time;
int MAXMOVES;
int *evalHash;
long int g_colls = 0;
long int g_ins = 0;
/* End Globals */

//#define TESTISWIN
//#define TESTTHREATS
//#define DBGAI_0
//#define TESTRUNS

int main ()
{
    struct position pos;
    struct move mv;
    // Fill in all of our global parameters above
    pos.board = readBoardVector ();
    // Initialize the eval hash
    evalHash = calloc(100000000, sizeof(int));

#ifdef TESTISWIN
    printf("isWin:\n");
// print board to verify
    int i,j;
    for (j = rows - 1; j >= 0; j--)
       for (i = 0; i < cols; i++) {
          printf("%c", CELL(pos.board,i,j,cols) );
          if (i == cols - 1)
              printf("\n");
       }
    printf("\n");
    printf("%d\n",isWin(pos.board));
    return 0;
#endif
#ifdef TESTTHREATS
    printf("eval:\n");
// print board to verify
    int i,j;
    for (j = rows - 1; j >= 0; j--)
       for (i = 0; i < cols; i++) {
          printf("%c", CELL(pos.board,i,j,cols) );
          if (i == cols - 1)
              printf("\n");
       }
    printf("\n");
    printf("%d\n",eval(&pos));
    return 0;
#endif
#ifdef TESTRUNS
    int a = runval("bsss");
    printf("bsss = %d\n",a);
    a = runval("bbgs");
    printf("bbgs = %d\n", a);
    a = runval("rrsg");
    printf("rrsg = %d\n", a);
    return 0;
#endif
    pos.nextMove = 'b';
/*
	//////////////////////////////////////////////////////////////
	////DIRTY HACK TO BEAT ODIN 5/////////////////////////////////

	//pos.board[rows*cols+1] = '\0';
	//printf("%s", pos.board);


	int i = 0;
	int j = 0;
	int k = 0;
	char match = 1;
	char teststring[] = "sssssssbrssssssssssssrbrbrrsbbrrbrsggsssssrrsssssbbsssss";
	for( i = 0; i < rows; i++)
	{
		for (j = 0; j < cols; j++)
		{	
			//printf("%d\n",k);
			if (pos.board[k] != teststring[(j*rows) + i])
			{
				match = 0;
				break;
				
			}
			k++;
		}
	}
	if (match)
	{
		mv.x = 6;
		mv.colour = 'b';
		printMove( &mv );
		return 0;
	}

	//////////END DIRTY HACK TO BEAT ODIN 5////////////////////////
	//////////////////////////////////////////////////////////////
*/



	
	mv = doSearch ( &pos );

    free ( pos.board );
    //printf("%d insertions, %d collisions\n", g_ins, g_colls);
    free (evalHash);
    printMove ( &mv );
    
    return 0;
}

char * readBoardVector ()
{
    int i, j;
    char *board;
    scanf("(%d,%d,%d,%d,%d,%d", &cols, &rows, &last_move,
                                &total_time, &player_1_time, &last_move_time);
    board = (char *) malloc ( rows * cols );
    MAXMOVES = 2 * cols;

	for (i = 0; i < cols; i++)
		for (j = 0; j < rows; j++) 
			scanf(",%c", &board[j*cols + i]);

    return board;
}

struct move doSearch ( struct position *pos )
{
    //TODO: reenable
    int d;
    int depth = getDepth ();
    int alpha = -INFINITY;
    int beta = INFINITY;
    struct move mv;

    // Run an iterative deepening alphaBeta:
    // use firstAlphaBeta for the first call since it returns an actual best move
    //TODO iterative deepening with hashing
    for ( d = depth; d <= depth; d++) {
        //TODO: check we have enough time left
        mv = firstAlphaBeta ( pos, d, alpha, beta );
    }
    return mv;
}

int getDepth ()
{
    // TODO: actually use the time to get the depth
    return 7;
}

// alphaBeta:
// performs an alpha-beta search to a specified depth
int alphaBeta (struct position *pos, int depth, int alpha, int beta)
{
	struct move list[MAXMOVES];
	int i, n, value;
    int bestValue = -INFINITY;

    if ( lookUp ( pos->board, &value ) )
        return value;

    if ( (value = isWin(pos->board )) != 0 ) {

        // TODO: use hashing in here too
        // DBG
        if ( pos->nextMove == 'b' )
           value *= -1;
#ifdef DBGAI
//        printf("%c:win value = %d\n",pos->nextMove,value*(INFINITY/5));
#endif
        insert ( pos->board, value * (INFINITY / 5));
		return (value * (INFINITY / 5));
    }

	if (depth == 0)	{
        //dbg
        //
		value = eval ( pos );
        // If are evaluating this position from red's perspective, negate
        // the value of the position
        if ( pos->nextMove == 'b' )
            value *= -1;
        //dbg
        insert ( pos->board, value );
        return value;
    }   
	n = getMoves ( pos, list );
    
	for ( i = 0; i < n; i++ ) {
        if( bestValue > alpha ) 
			alpha = bestValue;
		doMove ( &list[i], pos );
		value = -alphaBeta ( pos, depth - 1, -beta, -alpha);
		undoMove ( &list[i], pos );
		bestValue = MAX ( value, bestValue );
		if ( bestValue >= beta ) 
			break;
	}
	return bestValue;
}

struct move firstAlphaBeta (struct position *pos, int depth, int alpha, int beta)
{
	struct move list[MAXMOVES];
	int i, n, value, besti;
    int bestValue = -INFINITY;
    int immediateWin = 0;

	n = getMoves ( pos, list );
//TODO clean up this hack
    // Check if blue can win immediately
    for ( i = 0; i < n; i++ ) {
        doMove ( &list[i], pos );
        value = isWin ( pos->board );
        if ( value < 0 ) {
            immediateWin = 1;
            bestValue = MAX (value, bestValue);
            if ( value == bestValue )
                besti = i;
        } 
        undoMove ( &list[i], pos );
    }
    if (immediateWin)
        return list[besti];
    // Check if red is about to win
    for ( i = 0; i < n; i++ ) {
        if (list[i].colour == 'b')
            list[i].colour = 'r';
        doMove ( &list[i], pos );
        value = isWin ( pos->board );
        if ( value > 0 ) { //Only move!
            list[i].colour = 'b';
            return list[i];
        }
        undoMove ( &list[i], pos );
        if(list[i].colour == 'r')
            list[i].colour = 'b';
    }
//end hack
   
    bestValue = -INFINITY;
	for ( i = 0; i < n; i++ ) {
		doMove ( &list[i], pos );
		value = -alphaBeta ( pos, depth - 1, -beta, -alpha);
		undoMove ( &list[i], pos );
#ifdef DBGAI_0
        printf("i = %d | %c's move = (%d,%c) :: value=%d\n",i,pos->nextMove,list[i].x,list[i].colour,value);
#endif
		bestValue = MAX ( value, bestValue );
        if (value == bestValue)
            besti = i;
        }
        
	}
	return list[besti];
}

// TODO: maybe do some static move ordering in here and/or integrate it
//       with the killer move heuristic
int getMoves (struct position *pos, struct move *list)
{
    int8_t i, j;
    int n = 0;
    // Get valid columns
    for ( i = 0; i < cols; i++ ) {
        for ( j = 0; j < rows; j++ ) {
            if ( CELL(pos->board,i,j,cols) == 's' ) {
                list[n].x = i;
                list[n].y = j;
                list[n].colour = pos->nextMove;
                list[n+1].x = i;
                list[n+1].y = j;
                list[n+1].colour = 'g';
                n += 2;
                break;
            }
        }
    }
    return n;
}

void doMove (struct move *m, struct position *p)
{
    SETCELL (p->board, m->x, m->y, cols, m->colour);
    if (p->nextMove == 'b')
        p->nextMove = 'r';
    else
        p->nextMove = 'b';
}

void undoMove (struct move *m, struct position *p)
{
    SETCELL (p->board, m->x, m->y, cols, 's');
    if (p->nextMove == 'b')
        p->nextMove = 'r';
    else
        p->nextMove = 'b';
}

void printMove (struct move *mv)
{
    printf ( "(%d,%c)", mv->x + 1 , mv->colour ) ;
}

//TODO: get rid of this
//dbg: quick and dirty eval
int eval ( struct position *p )
{
    return threats ( p->board );
/*
    int i,j;
    int c=0;
    int val = 0;
    for(i=0; i<cols; i++) {
        for(j=0; j<rows; j++) {
            if (CELL(p->board,i,j,cols) == 's') {
                c = 1;
                break;
            }
            else if (CELL(p->board,i,j,cols) == 'b') {
                c++;
                val +=  c*c*((i+1)%(cols/2));
            }
            else if (CELL(p->board,i,j,cols) == 'r') {
                c++;
                val -= c*c*((i+1)%(cols/2));
            }
        }
    }
    c=0;
    for(j=0; j<rows; j++) {
        for(i=0; i<cols; i++) {
            if (CELL(p->board,i,j,cols) == 's')
                c = 1;
            else if (CELL(p->board,i,j,cols) == 'b') {
                c++;
                val +=  c*c*((i+1)%(rows/2));
            }
            else if (CELL(p->board,i,j,cols) == 'r') {
                c++;
                val -= c*c*((i+1)%(rows/2));
            }
        }
    }
    if (p->nextMove == 'b')
        val *= -1;
    return val;
*/
}

//TODO
int lookUp (char *board, int *value)
{
    unsigned int hash = 5381;
    unsigned int i    = 0;

    for(i = 0; i < rows*cols; board++, i++)
    {
       hash = ((hash << 5) + hash) + (*board);
    }
    if (*value = evalHash[hash%100000000]) 
        return 1;
    else
        return 0;
}

//TODO
int insert (char *board, int value)
{
    unsigned int hash = 5381;
    unsigned int i    = 0;

    for(i = 0; i < rows*cols; board++, i++)
    {
       hash = ((hash << 5) + hash) + (*board);
    }
    if (evalHash[hash%100000000])
        g_colls++;
    evalHash[hash%100000000] = value;
    g_ins++;
    return 0;
}


